BZOJ3876【JSOI2014】支线剧情 <带下界的费用流>

Problem

【JSOI2014】支线剧情

Background

宅男非常喜欢玩游戏，比如仙剑，轩辕剑等等。不过喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。
这些游戏往往都有很多的支线剧情，现在想花费最少的时间看完所有的支线剧情。

Description

现在所玩的游戏中，一共有个剧情点，由到编号，第个剧情点可以根据的不同的选择，而经过不同的支线剧情，前往种不同的新的剧情点。当然如果为，则说明号剧情点是游戏的一个结局了。
观看一个支线剧情需要一定的时间。一开始处在号剧情点，也就是游戏的开始。显然任何一个剧情点都是从号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。
由于过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，所以要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到号剧情点。可以在任何时刻退出游戏并重新开始。
不断开始新的游戏重复观看已经看过的剧情是很痛苦，希望花费最少的时间，看完所有不同的支线剧情。

Input

输入一行包含一个正整数。
接下来行，第行为号剧情点的信息：第一个整数为，接下来个整数对，和，表示从剧情点可以前往剧情点，并且观看这段支线剧情需要花费的时间。

Output

输出一行包含一个整数，表示看完所有支线剧情所需要的最少时间。

Sample Input

Sample Output

Explanation

需要重新开始次游戏，加上一开始的一次游戏，次游戏的进程是,,和。

Hint

的数据满足,,,

标签：带下界的费用流

Solution

无源无汇带下界最小费用可行流。

将原图直接放入网络流，其中每条边流量下界为，上界为；每个点向连一条流量下界为，上界为，费用为的边。这样就转化为求此图的最小费用可行流。
将原图中每条边拆一个流量为费用不变的边出来，这样若这条边满载后，只需要流量守恒即可。对于每个点，令入度为，出度为。则经过其的流量一定是。如此拆出来的流量为的边可以以出入度的限制的形式出现，而不必真正建出这些边使其满载。而对于入度和出度不等的边，我们新建源汇，从源点补流或分流到汇点即可。

建图：

对于原图中每条边长度，连边流量费用
对于非号点的点，连边流量费用
对于点，计算其入度和出度
- 若，连边流量费用
- 若，连边流量费用

跑最小费用最大流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300
#define MAX_M 20000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, s, t, tot, deg[MAX_N+5];
int cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que; bool inq[MAX_N+5]; int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front(); que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false; int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += flow*d[t]; return true;
}
int main() {
    read(n), init();
    for (int u = 1, k; u <= n; u++) {
        read(k);
        for (int i = 0, v, c; i < k; i++)
            read(v), read(c), addedge(u, v, INF, c), 
            deg[u]--, deg[v]++, tot += c;
        if (u^1) addedge(u, 1, INF, 0);
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0) addedge(s, i, deg[i], 0);
        else if (deg[i] < 0) addedge(i, t, -deg[i], 0);
    while (SPFA()) ;
    return printf("%d\n", mic+tot), 0;
}